package leetcode.d_200_299;

public class P279PerfectSquares {
    public static void main(String[] args) {
        P279PerfectSquares.Solution solution = new P279PerfectSquares().new Solution();
    }

    class Solution {
        public int numSquares(int n) {
            int[] dp = new int[n+1];
            dp[0] = 0;
            for (int i=1; i<=n; i++) {
                dp[i] = i;
                for (int j=1; j*j<=i; j++) {
                    dp[i] = Math.min(dp[i], dp[i-j*j]+1);
                }
            }
            return dp[n];
        }
    }
}
